package main.Q501_600;

import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Q551_560 {
    public static void main(String[] args) {
        System.out.println("Question551：学生出勤记录Ⅰ");
        System.out.println("Question552：");
        System.out.println("Question553：");
        System.out.println("Question554：");
        System.out.println("Question555：");
        System.out.println("Question556：下一个更大元素Ⅲ");
        System.out.println(new Question556().nextGreaterElement(230241));
        System.out.println("Question557：反转字符串中的单词Ⅲ");
        System.out.println("Question558：");
        System.out.println("Question559：N叉树的最大深度");
        System.out.println("Question560：和为K的子数组");
    }
}

class Node {
    public int val;
    public List<Node> children;
    public Node() {}
    public Node(int _val) {
        val = _val;
    }
    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}

class Question551{
    public static boolean checkRecord(String s) {
        char[] str=s.toCharArray();
        int lateCount=0,absentCount=0;
        for (int i=0;i<str.length;i++){
            if (str[i]=='A') {
                absentCount++;
                lateCount=0;
            }
            else if (str[i]=='L') lateCount++;
            else lateCount=0;
            if (lateCount==3) return false;
        }
        if (absentCount>=2) return false;
        else return true;
    }
}

class Question556{
    public int nextGreaterElement(int n) {
        char[] s = String.valueOf(n).toCharArray();
        for (int i = s.length - 1; i > 0; i--) {
            if (s[i] > s[i - 1]) {
                Arrays.sort(s, i, s.length);
                for (int j = i; j < s.length; j++) {
                    if (s[j] > s[i - 1]) {
                        char t = s[i - 1];
                        s[i - 1] = s[j];
                        s[j] = t;
                        long ans = Long.parseLong(String.valueOf(s));
                        if (ans > Integer.MAX_VALUE) return -1;
                        return (int) ans;
                    }
                }
            }
        }
        return -1;
    }
}

class Question557{
    public String reverseWords(String s) {
        String[] strs=s.split(" ");
        StringBuffer reverse=new StringBuffer();
        for (int i=0;i< strs.length;i++){
            StringBuffer temp=new StringBuffer(strs[i]);
            reverse.append(temp.reverse()+" ");
        }
        reverse.deleteCharAt(reverse.length()-1);
        return reverse.toString();
    }
}

class Question559{
    public int process(Node root){
        if (root==null) return 0;//头节点为空
        if (root.children.size()==0) return 1;//无孩子节点(即叶子节点)
        int max=0;
        for (Node node: root.children){//遍历孩子节点
            int temp=process(node);
            if (max<temp) max=temp;
        }
        return max+1;
    }
    public int maxDepth(Node root) {
        return process(root);
    }
}

class Question560{

    public int subarraySum(int[] nums, int k) {
        int result=0,pre=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        for(int i=0;i<nums.length;i++) {
            pre+=nums[i];
            if(map.containsKey(pre-k)) {
                result+=map.get(pre-k);
            }
            map.put(pre,map.getOrDefault(pre,0)+1);
        }
        return result;
    }

//    public static int subarraySum(int[] nums, int k) {
//        int count=0,length= nums.length;
//        int pre=0,next=0;
//        for (int i=0;i<length;i++){
//            for (int j=i;j<length;j++){
//                if (i==j) {
//                    pre=nums[j];
//                    if (pre==k) count++;
//                }
//                else {
//                    next=pre+nums[j];
//                    pre=next;
//                    if (next==k) count++;
//                }
//            }
//        }
//        return count;
//    }
}